package test5;

import java.util.HashMap;

/**
 * @Author Jun jie Yi
 * 2022/5/7 21:32
 */
public class Demo2 {
    public static void main(String[] args) {
        String s1 = "ab", s2 = "eidboaoo";
        System.out.println(minWindow(s1, s2));
    }

    public static boolean minWindow(String s1, String s2) {
        //做标记使用，key:字符类别 - value:数量
        HashMap<Character, Integer> need = new HashMap<>(s1.length());
        HashMap<Character, Integer> window = new HashMap<>(s1.length());
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = 0;
        int v = 0;
        while (r < s2.length()) {
            // c 是将移入窗口的字符
            char c = s2.charAt(r);
            // 右移窗口
            r++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);//计数器
                if (window.get(c).compareTo(need.get(c)) == 0)
                    v++;
            }
            //当字符种类数达标(注意：这里当 v = need.size() 的时候，被匹配的字符串所有字符都包括了)
            while (r - l >= s1.length()) {
                if (v == need.size()) return true;
                // d 是将移出窗口的字符
                char d = s2.charAt(l);
                // 左移窗口
                l++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).compareTo(need.get(d)) == 0)
                        v--;
                    window.put(d, window.get(d) - 1);//字符计数器 -1
                }
            }
        }
        return false;
    }
}
